import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;


public class Bipartite {
    public static void main(String[] args) {
        Solution s = new Solution();
    int[][] graph = new int[][]{{1,3},{0,2},{1,3},{0,2}};
        s.isBipartite(graph);
    }
}


class Solution {
    Set<Integer> set0 = new HashSet<>();
    Set<Integer> set1 = new HashSet<>();
    boolean[] isVisited;
    public boolean isBipartite(int[][] graph) {
        isVisited = new boolean[graph.length];
        Arrays.fill(isVisited, false);
        for (int i = 0; i < graph.length; i++) {
            if(isVisited[i]==false){
                boolean re = search(graph, i);
                if(re==false) return false;
            }
        }
        return true;
   }

   public boolean search(int[][] g,int start){
       isVisited[start]=true;
        for (int p : g[start]) {
            if(p<start) continue;
            if(set0.contains(p)){
                if(set1.contains(p)){
                    return false;
                }else{
                    if(set1.contains(start)) return false;
                    set1.add(p);
                }
            }else{
                if(set0.contains(start)) return false;
                set0.add(p);
            }
            boolean result = search(g, p);
            if(result==false) return false;
        }
        return true;
   }
}